PAC Learning(Probably Approximately Correct Learning)

• $0<\delta <1/2$: 최소한 $1-\delta$의 확률로,
• $0<ϵ<1/2$: $ϵ$보다 작은 그러한 error를 가지는 hypothesis space의 $h$를 찾을 수 있음을 의미한다.

기본적으로 instance space $J$에서 비롯된 distribution $D$에 대하여, 진리 함수(target concept) $c$를 설명 가능한 $h$를 찾을 수 있음을 의미한다.

이를 만족시키는 필요한 train data의 크기 $N$은, $1/ϵ$, $1/\delta$, $|J|$, |c|의 term으로 표현되는 다항식으로 나타난다.